#include "lt_LM.h"
#include <stdlib.h>

point l_p;

// find_down_point return index of left x, lowest y point
int find_down_point(point * & p, int n)
{
   int low  = 0;
   for (int i = 0; i < n; i++)
      if (p[i].y < p[low].y || (p[i].y == p[low].y && p[i].x < p[low].x))
         low = i;
   return low;
}

// compare function
int cmp(const void * a, const void * b)
{
   point ap = *(point*)a;
   point bp = *(point*)b;
   int lt = left_turn(ap, l_p, bp);
   if (lt != 0)
      return lt;
   if (ap.y < bp.y)
      return -1;
   if (ap.y > bp.y)
      return 1;
   if (ap.x < bp.x)
      return -1;
   if (ap.x > bp.x)
      return 1;
   return 0;
}

// graham scan
std::vector<point> graham_scan(point * & p, int n)
{
   std::vector<point> ch;
   if (n < 2)
   {
      if (n == 1)
         ch.push_back(p[0]);
      return ch;
   }

   l_p = p[find_down_point(p, n)];
   qsort(p, n, sizeof(point), cmp);

   ch.push_back(p[0]);
   ch.push_back(p[1]);

   for (int i = 2; i < n; i++)
   {
      while (ch.size() >= 2 && left_turn(ch[ch.size() - 2], ch[ch.size() - 1], p[i]) <= 0)
         ch.pop_back();
      ch.push_back(p[i]);
   }

   if (ch[0].x == ch[1].x && ch[0].y == ch[1].y)
      ch.pop_back();

   return ch;
}